
\subsection{Randomization Component}


\begin{figure*}[t]
\centering
\includegraphics[scale=0.7]{Example2.eps}
\caption{Randomization Record Structure and Update}
\end{figure*}


\noindent \textbf{Randomization Record Used in Our Randomization.}
%We track several pieces of information relevant to the data
%structure definitions as well as data structure instances as the
%internal data structure used in our randomization. In particular,
%Randomization record is a piece of metadata inserted by SALADS for
%each data structure instance.
A randomization record contains the
field information: \texttt{$F_o$} (Field Offset), \texttt{$F_s$}
(Field Size) and \texttt{$F_r$} (Field Randomization Flag).
\texttt{$F_r$} marks whether the field can be randomized. Let's
recall the flexible array field mentioned in Section 3.1, we will
mark it un-randomizable, as such its $F_r$ will be set (0 represents
randomizable and 1 represents un-randomizable). A randomization record
also contains the runtime status of the data structure instance:
\texttt{$I_c$} (Instance Operation Count), \texttt{$I_a$} (Instance
Address) and \texttt{$I_k$} (Randomization Seed). $I_k$ has two
specific values: zero indicates the data structure instance keeps
original layout and -1 indicates the data structure instance cannot
be randomized.  $I_c$ is the number of operations executed on the
data structure instance. For determining when to re-randomize the
data structure, we set a threshold for the re-randomization timing
window named $W_m$, when $I_c$ exceeds the $W_m$, we will
re-randomize the data structure instance. As there are multiple data
structure definitions, and multiple data structure instances, we use
a hash table to organize these information based on the index of the
data structure definitions we assigned during the AST-Pass.



%
%
%\subsubsection{Structure of randomization record}
%Randomization record maintains the key for each data structure instance and
%the necessary information for dynamically changing the key. Figure 3
%(a) shows the structure of the randomization record. The randomization record contains
%six arrays: \texttt{$I_c$}(Instance Count), \texttt{$I_a$}(Instance
%Address), \texttt{$I_k$}(Instance Key), \texttt{$F_o$}(Field
%Offset), \texttt{$F_r$} (Field Reference) and \texttt{$F_s$} (Field
%Size). The six arrays can be classified into two categories, one is
%related to the fields ($F_o$,$F_r$ and $F_s$) and the other is
%related to the instances ($I_c$, $I_a$ and $I_k$). \texttt{$I_c$},
%\texttt{$I_a$} and \texttt{$I_k$} are two-dimensions arrays, they
%record the three information for each instance: number of executed
%operations, the address and the key. One dimension (0...n)
%represents the index of the data structure, the other dimension
%(0...m) represents the index of the instance. ``n" represents the
%total number of data structure in the program and ``m" represents
%the maximum number of instances to be randomized for each data
%structure. ``n" can be calculated by the analysis component and ``m"
%is set by the user. \texttt{$F_o$}, \texttt{$F_r$} and
%\texttt{$F_s$} are also two-dimensions arrays, they record the three
%information for each data structure's fields: the offset of the
%field, the flag that indicates whether the field can be randomized
%and the size of the field. One dimension (0...n) represents the
%index of the data structure, the other dimension (0...l) represents
%the index of the field. ``l" is the maximum field number calculated
%by analysis component. \texttt{$F_r$}  marks the field to indicate
%whether it can be randomized(``0" represents the field can be
%randomized, and ``1" represents the field can not be randomized).
%\texttt{$F_s$} is used to cluster the fields based on their size,
%because we need to switch the field data with the same size to
%prevent it truncating or filling out the fields due to the different
%size, it guarantees the accurately access to the randomized fields.
%Using the size-clustering randomization method, the total
%possibility of the fields randomization for one data structure
%instance can be calculated by the formula: P=$\prod_{i=1}^{\Theta}
%f(i)$, $f(i)=A_{m_i}^{m_i}$. $\Theta$ indicates the total categories
%of type size. \texttt{$m_i$} indicates the number of fields with the
%size \texttt{i}.

%
%\subsubsection{randomization record Generation} Based on the structure of
%the randomization record, SALADS allocates six global
%arrays (\texttt{$I_c$},\texttt{$I_a$}, \texttt{$I_k$},
%\texttt{$F_r$}, \texttt{$F_o$} and \texttt{$F_s$}) into the program
%to store the randomization record, and defines two routines
%\texttt{Mapping\_Update} and \texttt{Rand\_Conv} for the data
%structure randomization manipulation. \texttt{Mapping\_Update} is
%used to update the randomization record and reorder the fields.
%\texttt{Rand\_Conv} is used to calculate the difference between
%randomized offset and the original offset. By inserting the global
%variables and functions into the program, we write a gcc plugin
%which is the new feature since gcc-4.5.0\cite{GCCPlugins}. The gcc
%plugin can be invoked at pre-determined events in the compilation
%process. In our plugin, we select the event
%\texttt{PLUGIN\_START\_UNIT} to creates the global variables and
%functions. Note that \texttt{PLUGIN\_START\_UNIT} callback is after
%the front-end of the GCC initialization (e.g., integer\_type\_node),
%and before the gimple pass ``\texttt{ds\_randomization}" that we use
%to data structure randomization. The GCC plugin assigns the tree
%nodes that point to the global variable and function, after which
%the tree nodes will be used in ``\texttt{ds\_randomization}".


%\subsubsection{Data Structure Layout Randomization}
%To randomize the layout for each data structure
%instance, we add the Gimple Pass-1 \texttt{DS\_Randomization} in \texttt{gcc}.%The key idea of SALADS is to randomize the layout
%for each data structure instance by modifying the data structure
%operation to enable it having two functions: updating the seed for
%each data structure instance and reordering the fields
%correspondingly. To this end, we add a gimple pass
%\texttt{DS\_Randomization} in \texttt{gcc}.




\vspace{0.1in} \noindent \textbf{Data Structure Layout
Randomization.} A challenge here is a data structure could have a
nested definition (i.e., one data structure field is defined from
another data structure) and this is very common (e.g., about 80\%
data structure
operations are nested in Linux kernel). %If one data structure
%instance inside the nested definition is failed to be recognized,
%its memory layout will be handled inconsistently and propagate the
%fault to its nested-instance (the field instance in it).
To solve this challenge, we propose the instances extraction method,
named \texttt{Parse} presented in Algorithm 1, to identify
all the involved instances in one expression. Specifically, %when parsing the gimple statement,
%we classify the data structure instance into three categories:
%direct instance (line 5-8), array instance (line 9-14) and indirect
%instance (line 15-20).
\texttt{Parse} recursively iterates each operand in the expression
(line 8 and line 10) and records each data structure operation to
$N_r$, the address of instance to \texttt{$N_a$} and the field to
\texttt{$N_f$} (line 5-7). For the nested data structure, we
randomize the outer instance first, e.g., for data structure
instance operation \texttt{A->B.x}, we will first randomize the
layout for \texttt{A} and then \texttt{B}. Such order (line 16)
matches the definition of the data structure.


\texttt{DS\_Randomization} (in Algorithm 1) is the method to
randomize each data structure instance. At high level, it iterates
every program statement (expression statement or control
statement\footnote{We follow the classification of program statement
in \cite{CPrimer}.}), and parses each expression involved in the
statement % to get the
%data structure instance as well as the field information based on \texttt{Parse} routine. % using the
%\texttt{Parse} routine. %Next it invokes \texttt{Update\_Mapping} to
%re-organize the data structure layout for each data structure
%instance.
based on \texttt{Parse}. We then iterate each data structure
instance (line 16-21). First, we fill out the corresponding field
information in randomization record, including $F_o$, $F_s$
and $F_r$ (line 17). %At the compilation time, we
%can not predict which operation will be executed before the others,
%so we can not initialize the data structure information before one
%specific operation.
Next, we insert the routine named \texttt{Update\_Record} (presented
in Algorithm 2) before the data structure operations and this
routine will update the runtime status of the data structure
instance ($I_c$, $I_a$ and $I_k$) in randomization record. After
\texttt{Update\_Record}, we insert a routine named
\texttt{Offset\_Diff} before the examined statement to calculate the
distance between the randomized offset and original offset (line
19), and finally we replace the original operation (line 20) with
the new one that can access randomized field. In our prototype,
\texttt{DS\_Randomization} is implemented as a gimple pass in
\texttt{gcc}.


For our \texttt{Update\_Record} routine (in Algorithm 2), we take
the index $\theta$ of the examined data structure definition, and
the address of the corresponding instance \texttt{$N_a$} as the
parameters. We search in the \texttt{$I_a$} in our randomization record
to check whether the instance with address \texttt{$N_a$} exists. If
not (line 3-6), we put the \texttt{$N_a$} in
\texttt{$I_a$[$\theta$][$\tau$]}, and randomly select a seed
$\gamma$ to \texttt{$I_k$[$\theta$][$\tau$]}. Based on the seed
$\gamma$, we reorder the fields (line 5). Otherwise (line 7-11), we
compare \texttt{$I_c$[$\theta$][$\tau$]} with our re-randomization
timing windows $W_m$ (recall we will dynamically change the layout
for each data structure instance from time to time and $W_m$ is the
threshold to control the re-randomization), and check whether $W_m$
number of operations have been executed since last seed updating
(line 7). If so, we check whether the instance can be randomized
(\texttt{$I_c$[$\theta$][$\tau$]}$>$=0) since de-randomization
component (Section 3.3) will mark the instance involved in pointer
assignment as un-randomizable. If so, we update the seed (line 8 and
line 10), and reorder the fields based on the new seed (line 9). If
\texttt{$I_c$[$\theta$][$\tau$]} is less than $W_m$, we will
increase the operation number and keep the seed unchanged (line 11).
%\texttt{Reorder\_Fields} is used to reorder the fields based on the
%old seed (\texttt{$Seed_1$})
%and the new seed (\texttt{$Seed_2$}). %Another inserted routine
%\texttt{Offset\_Diff} (line 19 in Algorithm 1), calculates the
%distance between the randomized offset and original offset based on
%the index $\theta$ of the examined data structure definition and the
%corresponding field \texttt{$N_f$}.

%When we encounter the data
%structure instance operations, we compare the current instance
%address with existing instances which have the same data structure
%type, if it is the new one, we add the record for the instance in
%the randomization record, assign the random key and reorder the fields. If
%the data structure instance exists, we update the key based on the
%re-randomization window, and reorder the fields according to the new
%key. The re-randomization window $W_m$, which represents the maximum
%number of executed data structure operations to change the random
%key, is selected by the user. The more $W_m$ is, the more
%randomization rate will be, definitely security bar will be higher,
%but it will introduce more performance overhead; vice versa. After
%\texttt{Update\_Mapping}, we insert the routine named
%``\texttt{Rand\_Conv}" before the statement to calculate the offset
%of the randomized field, and finally we replace the original
%operation with the new one that can access randomized field.
%
%
%
%Algorithm 1 is the data structure modification algorithm. It
%consists two routines: \texttt{Parse} and
%\texttt{DS\_Randomization}. \texttt{Parse} is the routine that
%records all the data structure instances by parsing the operand of
%the gimple statement. \texttt{Randomization} is the routine that
%randomizes each data structure instance by updating the randomization record
%and the data structure operation. For each operand of the gimple
%statement, the data structure instance has tree kinds: direct
%instance(line 5-8), array instance (line 9-14) and indirect instance
%(line 15-20). \texttt{Parse} records the data structure instance
%operation \texttt{$N_r$} and field \texttt{$N_f$} (line 6,11,17).
%For the nested data structure, we randomize the outer instance
%first, take ``\texttt{A->B.x}" for instance, we first randomize the
%``A" and then randomize the ``B". The order matches the definition
%of the data structure. \texttt{DS\_Randomization} contains key
%mapping initialization (line 27), randomization record update (line 28) and
%calculates the randomized offset to the data structure instance
%operation (line 29-30). The randomization record initialization (line 27)
%inserts the gimple statements to initialize the $F_o$, $F_s$ and
%$F_r$, which has been calculated by Pass 1. \texttt{Update\_Mapping}
%(line 28) and \texttt{rand\_conv} (line 29) are inserted into the
%programs by SALADS, and its function will be illustrated in
%Algorithm 2.
%
% Since one statement may contain more than one data
%structure instance (e.g.,the nested data structure), we retrieve all
%of them from the outer one to the inner one. As such one statement
%may be modified multiple times since it contains different data
%structure instances. For each data structure instance, we record the
%tree that represents the data structure operation, named
%\texttt{$N_r$}, including the instance address \texttt{$N_a$} and
%the data structure field \texttt{$N_f$}.
%
%
%In ``\texttt{ds\_randomization}", we reference the arrays created by
%our plugin by the expression which passes the VAR\_DECL to
%build\_fold\_addr\_expr. The pseudo code for
%``\texttt{ds\_randomization}" is shown in Algorithm 1: first it
%iterates every gimple statement based on the basic block, then it
%parses the data structure statement to get the data structure
%instance and its field based on \texttt{Parse} in Algorithm 1. Since
%one statement may contain more than one data structure instance
%(e.g.,the nested data structure), we retrieve all of them from the
%outer one to the inner one. As such one statement may be modified
%multiple times since it contains different data structure instances.
%For each data structure instance, we record the tree that represents
%the data structure operation, named \texttt{$N_r$}, including the
%instance address \texttt{$N_a$} and the data structure field
%\texttt{$N_f$}.
%
%
%
%
%Algorithm 1 is the data structure modification algorithm. It
%consists two routines: \texttt{Parse} and
%\texttt{DS\_Randomization}. \texttt{Parse} is the routine that
%records all the data structure instances by parsing the operand of
%the gimple statement. \texttt{Randomization} is the routine that
%randomizes each data structure instance by updating the randomization record
%and the data structure operation. For each operand of the gimple
%statement, the data structure instance has tree kinds: direct
%instance(line 5-8), array instance (line 9-14) and indirect instance
%(line 15-20). \texttt{Parse} records the data structure instance
%operation \texttt{$N_r$} and field \texttt{$N_f$} (line 6,11,17).
%For the nested data structure, we randomize the outer instance
%first, take ``\texttt{A->B.x}" for instance, we first randomize the
%``A" and then randomize the ``B". The order matches the definition
%of the data structure. \texttt{DS\_Randomization} contains key
%mapping initialization (line 27), randomization record update (line 28) and
%calculates the randomized offset to the data structure instance
%operation (line 29-30). The randomization record initialization (line 27)
%inserts the gimple statements to initialize the $F_o$, $F_s$ and
%$F_r$, which has been calculated by Pass 1. \texttt{Update\_Mapping}
%(line 28) and \texttt{rand\_conv} (line 29) are inserted into the
%programs by SALADS, and its function will be illustrated in
%Algorithm 2.
%
%
%Algorithm 2 demonstrates how the routine \texttt{Mapping\_Update}
%works. When we encounter the data structure operation, we extract
%the address of the instance \texttt{$N_a$}. We search in the
%\texttt{$I_a$[$\theta$]} to check whether the instance with address
%\texttt{$N_a$} exists. If the instance firstly occurs (line 4-7), we
%put the \texttt{$N_a$} in \texttt{$I_a$[$\theta$][$\Tau$]}, and
%randomly select one key $\gamma$ to \texttt{$I_k$[$\theta$][$\Tau$]}.
%Based on the key $\gamma$, we reorder the fields (line 6). If the
%instance exists(line 8-16), we compare \texttt{$I_c$[$\theta$][i]}
%with the re-randomization windows $W_m$, and check whether  $W_m$
%operations has been executed since last key updating (line 9). If
%so, we update the key (line 11,13), reorder the fields based on the
%new key (line 12). If \texttt{$I_c$[$\theta$][i]} is less than
%$W_m$, we will increase the operation number and keep the key
%unchanged (line 14). \texttt{Reorder\_fields} is the routine to
%reorder the fields based on the original key \texttt{$key_1$} and the
%new key ($key_2$). We reorder the fields based on the field size
%\texttt{$F_s$} (line 19), and allocate two temporary arrays
%\texttt{$O_1$} and \texttt{$O_2$} to store the offsets that are
%calculated by $key_1$ and $key_2$. We show the method how the key controls
%the order of the fields.(line 25), another inserted routine
%\texttt{rand\_conv} (line 29 in Algorithm 1) uses the same
%key-control method to calculate the offset of the randomized field,
%then it gets the distance between the randomized offset and original
%offset.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{table}[t]
\begin{tabular}{|l|l|}\hline
\textbf{Algorithm 1: Data Structure Layout Randomization} &
\textbf{Algorithm 2: Updating Randomization Record}\\\hline

\begin{minipage}[t]{3.2in}
%\begin{algorithm}
%\caption{Data Structure Modification}          % give the algorithm a caption

\begin{algorithmic}[1]                  % enter the algorithmic environment
\begin{scriptsize}
\STATE /* \emph{stmt}: program statement; \emph{E},\emph{E'}:
program expression; \emph{$N_r$}: the data structure operation;
\emph{$N_i$}: the data structure instance; \emph{$N_f$}: the data
structure fields; \emph{$N_a$}:the  addresses of data structure
instances; \emph{FIELD($E$)}: extracting the field from $E$;
\emph{INST($E$)}: extracting the instance from $E$;
\emph{ADDR($N_i$)}: extracting the address from instance $N_i$;
\emph{OPERAND($E$,i)}: the $i_{th}$ operand of $E$; \emph{$D_c$}:
the number of the data structure instances.
*/
\end{scriptsize}
\begin{scriptsize} \STATE \textbf{Parse}(\emph{E},\&\emph{$D_c$})\{
   \STATE \quad \textbf{if} \emph{E} is a data structure operation
   \textbf{then}
   \STATE \qquad \emph{$N_i$} $\leftarrow$
\emph{INST($E$)}; \STATE \qquad \emph{$N_r$}[\emph{$D_c$}]
$\leftarrow$ \emph{$E$}; \STATE \qquad
\emph{$N_a$}[\emph{$D_c$}]$\leftarrow$\emph{ADDR}(\emph{$N_i$});
\STATE \qquad \emph{$N_f$}[\emph{$D_c$}++] $\leftarrow$
\emph{FIELD($E$)};

\STATE \qquad \textbf{Parse}(\emph{$N_i$},\&\emph{$D_c$});

 \STATE \quad \textbf{else}
 \STATE \qquad \textbf{for} \textbf{each} \emph{$E'$}$\leftarrow$\emph{OPERAND}(\emph{E},\emph{i})
 \textbf{do} \textbf{Parse} (\emph{$E'$},\&\emph{$D_c$}); \textbf{end for}
\STATE \quad \textbf{endif}
   \STATE \}
\STATE \textbf{DS\_Randomization}(\emph{stmt})\{  \STATE \quad
\textbf{for}
 \textbf{each} \emph{E} in \emph{stmt} \textbf{do} \STATE \qquad \emph{$D_c$}$\leftarrow$0;
 \textbf{Parse}(\emph{E},\&\emph{$D_c$});

\STATE \qquad \textbf{for} i=\emph{$D_c$}-1 to 0 \textbf{do}
  \STATE \qquad \quad Initializing the \emph{$F_o$},\emph{$F_s$} and \emph{$F_r$};
  \STATE \qquad \quad Update\_Record(\emph{$\theta$},\emph{$N_a$}[i]);
  \STATE \qquad \quad offset $\leftarrow$ Offset\_Diff(\emph{$\theta$},\emph{$N_f$}[i]);
  \STATE \qquad \quad replace \emph{$N_r$}[i] with
  \emph{$N_r$}[i]+offset;
   \STATE \qquad \textbf{end for} \STATE \quad \textbf{end for}\STATE\}
\end{scriptsize}
\end{algorithmic}

%\end{algorithm}
\end{minipage}
 &

\begin{minipage}[t]{3.2in}
%\begin{algorithm}
%\caption{Updating randomization record}          % give the algorithm a caption
\begin{algorithmic}[1]                 % enter the algorithmic environment
%\REQUIRE $JOP$, $R\_Set$,
\begin{scriptsize}
\STATE /* \emph{$N_a$}: instance address; \emph{$F_s$}: field size;
\emph{$F_o$}: field offset; \emph{$F_r$}: field randomization flag;
\emph{$I_c$}: instance operation number; \emph{$I_a$}: instance
address; \emph{$I_k$}: instance seed; \emph{$\theta$}: data
structure index; \emph{$\tau$}: the index of the instance with
address \emph{$N_a$}; \emph{$O_1$},\emph{$O_2$}: temporary buffers
store the field offset; \emph{temp}: temporary buffers store the
field's contents.
*/
\end{scriptsize}
\begin{scriptsize}
\STATE \textbf{Update\_Record}($\theta$,$N_a$)\{

\STATE \quad \textbf{if} \emph{$N_a$} $\notin$
\emph{$I_a$}[\emph{$\theta$}] \textbf{then} \STATE \qquad randomly
select \emph{$\gamma$}$>$0 to
\emph{$I_k$}[\emph{$\theta$}][\emph{$\tau$}]; \STATE \qquad
\textbf{Reorder\_Fields}($\theta$,\emph{$N_a$},0,\emph{$I_k$}[\emph{$\theta$}][\emph{$\tau$}]);
\STATE \qquad $I_c$[$\theta$][$\tau$]$\leftarrow$1;
\emph{$I_a$}[\emph{$\theta$}][\emph{$\tau$}]$\leftarrow$\emph{$N_a$};

\STATE \quad \textbf{else} \textbf{if}
(\emph{$I_c$}[\emph{$\theta$}][\emph{$\tau$}]==$W_m$\&\&
\emph{$I_k$}[\emph{$\theta$}][\emph{$\tau$}]$>$=0) \textbf{then}
 \STATE \qquad
\quad randomly select \emph{$\gamma$}$>$0 to update
\emph{$I_k$}[\emph{$\theta$}][\emph{$\tau$}]; \STATE \qquad \quad
\textbf{Reorder\_Fields}(\emph{$\theta$},\emph{$N_a$},\emph{$I_k$}[\emph{$\theta$}][\emph{$\tau$}],\emph{$\gamma$});
\STATE \qquad \quad
\emph{$I_k$}[\emph{$\theta$}][\emph{$\tau$}]$\leftarrow$
\emph{$\gamma$};
\emph{$I_c$}[\emph{$\theta$}][\emph{$\tau$}]$\leftarrow$0; \STATE
\quad \textbf{else} \emph{$I_c$}[\emph{$\theta$}][\emph{$\tau$}]++;
\STATE \quad \textbf{end if}

\STATE\} \STATE
\textbf{Reorder\_Fields}(\emph{$\theta$},\emph{$N_a$},\emph{$Seed_1$},\emph{$Seed_2$})\{
\STATE \quad i$\leftarrow$ 0; \emph{$\delta$}$\leftarrow$ 1; \STATE
\quad \textbf{for} each field \emph{$\delta$} with
\emph{$F_r$}[\emph{$\theta$}][\emph{$\delta$}]==0 \textbf{do}
 \STATE
\qquad
\emph{$O_1$}[i]$\leftarrow$\emph{$F_o$}[\emph{$\theta$}][\emph{$\delta$}];
\emph{$O_2$}[i]$\leftarrow$\emph{$F_o$}[\emph{$\theta$}][\emph{$\delta$}];
i++; \STATE \quad \textbf{end for}

\STATE \quad \textbf{if}{(\emph{$Seed_1$}$>$0 \&\& i$>$1)}
\textbf{then}
%\STATE \qquad \textbf{for} m=i to 1 \textbf{do} $O_1$[$Seed_1$\%m]
%$\leftrightarrow$ $O_1$[m-1]; \textbf{end for}
recalculate \emph{$O_1$} based on \emph{$Seed_1$}; \STATE \quad
\textbf{end if}


\STATE \quad \textbf{if}{(\emph{$Seed_2$}$>$0 \&\& i$>$1)}
\textbf{then}
%\STATE \qquad \textbf{for} m=i to 1 \textbf{do} $O_2$[$Seed_2$\%m]
%$\leftrightarrow$ $O_2$[m-1];  \textbf{end for}
recalculate \emph{$O_2$} based on \emph{$Seed_2$}; \STATE \quad
\textbf{end if}


\STATE \quad \textbf{for} m=0 to i-1 \textbf{do} \emph{temp}[m]
$\leftarrow$
*(\emph{$N_a$}+\emph{$O_1$}[m]); \textbf{end for}

\STATE \quad  \textbf{for} m=0 to i-1 \textbf{do}
*(\emph{$N_a$}+\emph{$O_2$}[m])$\leftarrow$ \emph{temp}[m];  \textbf{end for}

\STATE \}
\end{scriptsize}
\end{algorithmic}

%\end{algorithm}
\end{minipage}\\\hline
\end{tabular}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%










%\subsubsection{Putting Together}

\vspace{0.1in}
\noindent \textbf{Example. } Let's again take our working example, in particular the
\texttt{$p-$$>$$a$=1} data structure operation in Figure 2(a) to illustrate how we
dynamically change the layout. %the dynamic data
%structure randomization works in Figure 3 (b).
Suppose we have identified the data structure definition of
\texttt{TEST} (with an index 0) from our AST-Pass. %, and it has
%five fields.
Then, we build the randomization record for the data structure
\texttt{TEST}, including \texttt{$I_c$}, \texttt{$I_a$},
\texttt{$I_k$}, \texttt{$F_s$}, \texttt{$F_o$} and \texttt{$F_r$},
and these metadata definitions are shown in Figure 3(a).
%Since there is no pointer dereference the data structure fields, we
%assume every fields of \texttt{TEST} can be randomized.
When we encounter the data structure operation
\emph{\texttt{$p-$$>$$a$=1}}, \texttt{Parse} routine in Algorithm 1
will initialize \texttt{$N_a[0]$} with \texttt{p}, \texttt{$N_f[0]$}
with \texttt{a} and \texttt{$N_r[0]$} with \texttt{$p-$$>$$a$} (Line
5-7 in Algorithm 1). Next, we initialize the field information
$F_s$, $F_o$ and $F_r$ (the contents shown in Figure (a)). Then we
step into \texttt{Update\_Record(0}, \texttt{$N_a$[i])}(line 18 in
Algorithm 1). The work flow (1), (2), (3) in Figure 3(b)
demonstrates how \texttt{Update\_Record} works in the program. In
particular, it will update the \texttt{$I_c$} to 1, record the
address of instance in \texttt{$I_a$} (line 6 in Algorithm 2) and
randomly select a seed (e.g., 30) to \texttt{$I_k$} (line 4 in
Algorithm 2). Now, the \texttt{$Seed_1$} is 0 and \texttt{$Seed_2$}
is 30, and we step into the work flow (4) based on the
\texttt{Reorder\_Fields} routine (line 14-25 in Algorithm 2), we
randomize the order of the fields, and the results can be seen in
$O_2$ in Figure 3(b). %Note here $O_2$ is a temporary
%buffer used during program execution.
After randomization record updated, work flow (5) in Figure 3(b)
further calculates the difference between the randomized offset
($O_2$) and original offset ($F_o$), which is achieved by routine
\texttt{Offset\_Diff} (line 19 in Algorithm 1 ). Finally, by using
the offset difference (+8) we modify the data structure operation to
access the randomized field.
